package formal.linkedList;

/**
 * 反转链表
 *
 * @author DengYuan2
 * @create 2021-01-06 19:35
 */
public class E_206 {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        ListNode listNode = reverseList2(n1);
        System.out.println(listNode);
    }

    /**
     * 我的写法-迭代-头插法
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        ListNode first = new ListNode(-1);
        ListNode tmp = head;
        while (tmp != null) {
            head = head.next;
            tmp.next = first.next;
            first.next = tmp;
            tmp = head;
        }
        return first.next;
    }

    /**
     * 官方-递归
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        ListNode listNode = reverseList2(next);
        next.next=head;
        head.next=null;
        return listNode;
    }

    /**
     * 官方-迭代
     * @param head
     * @return
     */
    public static ListNode reverseList3(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode tmp = cur.next;
            cur.next=pre;
            pre=cur;
            cur=tmp;
        }
        //注意：这里返回的是pre哦
        return pre;
    }

}

